from typing import List


class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left, right, cur = 0, len(nums) - 1, len(nums) - 1
        ans = [0] * len(nums)
        while left <= right:
            if abs(nums[left]) > abs(nums[right]):
                ans[cur] = nums[left] ** 2
                left += 1
            else:
                ans[cur] = nums[right] ** 2
                right -= 1
            cur -= 1
        return ans

    def sortedSquares2(self, nums: List[int]) -> List[int]:
        '''
        在python用重排序好像更快
        '''
        ans = []
        for i in nums:
            ans.append(i*i)
        ans.sort()
        return ans